//
// Created by 高炎 on 2024/7/28.
// 实现的是升序排序
//
#include "iostream"
#include "vector"

using namespace std;

void BubbleSort(vector<int> a) {
    for (int i = 0; i < a.size() - 1; ++i) {
        // 外层循环完成一次就将最小(大)的元素放到了最前面的 i 位置
        for (int j = a.size() - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << ",";
    }
    cout << endl;
}

// 改进版冒泡排序;避免一些无意义的比较和判断
void BubbleSort2(vector<int> a) {
    bool flag = true;
    for (int i = 0; i < a.size() - 1 && flag; ++i) {
        // 如果比较过一轮或者几轮之后，再进行比较时，发现内层循环遍历一遍之后没有发生任何交换，说明此时已经有序，直接结束外层循环了
        flag = false;
        for (int j = a.size() - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                flag = true;
            }
        }
    }
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << ",";
    }
    cout << endl;
}


int main() {
//    vector<int> a = {1, 2, 3, 4, 5, 6};
    // 生成一个无序的数组
    vector<int> a = {3, 8, 7, 9, 0, 3, 1, 2};
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << ",";
    }
    cout << endl;
    BubbleSort2(a);


    return 0;
}